package arrays;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**题目：最长连续正数序列长度
 * y: 8 4 2 1 2 3 6  最大为4：1 2 3 4
 *
 * @Author Gavin
 * @date 2022.01.23 17:27
 */
public class array_18 {
    /**
     * 解题思路：
     * 第一种：先把数组排序，然后遍历，使用一个指针和两个变量len,max
     * 主要就是处理当指针p和p+1指向的元素是否差值为1或者差值相等的情况
     */
    public static int solution_1(int[] nums){
        if(nums==null||nums.length==0)return 0;
        Arrays.sort(nums);
        int max=0,p=0;
        while (p<nums.length-1){
            int len=1;
            while (p<nums.length-1){
                if(nums[p+1]-nums[p]==0){
                    ++p;
                    continue;
                }
                //差值大于1就跳出循环
                if(nums[p+1]-nums[p]!=1)break;
                //小于等于1的时候
                if(nums[p+1]-nums[p]==1)++len;
                ++p;
            }
            max=Math.max(max,len);
            ++p;
        }
        return max;
    }
    public static void main(String[] args) {
        int[] arr=new int[]{1,2,3,4,4,5,6};
        System.out.println(solution_1(arr));
    }
    /**
     * 第二种方法：使用一个辅助集合set来处理
     * 先把数组元素都放入集合中，然后遍历数组，把符合条件的元素从set集合中移除
     */
    public int solution_2(int[] nums){
        if(nums==null||nums.length==0)return 0;
        Set<Integer> set=new HashSet<>();
        int max=0;
        for(int num:nums)set.add(num);
        for (int i = 0; i < nums.length&&!set.isEmpty(); i++) {
            set.remove(nums[i]);
            int low=nums[i],high=nums[i];
            while (set.contains(--low))set.remove(low);
            while (set.contains(++high))set.remove(high);
            max=Math.max(max,high-low-1);
        }
        //1234
        return max;
    }
}
